Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Meta Medium Problems
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Maximum Swap

Problem Statement

Given a non-negative integer num, return the maximum number, which you can create by swapping any two digits of the number only once. If no swaps can improve the number, return the original number.

Examples

  1. Example 1:

    • Input: 2736
    • Expected Output: 7236
    • Justification: Swapping the first and second digits (2 and 7) results in the largest possible number.
  2. Example 2:

    • Input: 9965
    • Expected Output: 9965
    • Justification: The number is already in its maximum form, so no swap is needed.
  3. Example 3:

    • Input: 7281912
    • Expected Output: 9281712
    • Justification: Swapping the first digit (7) with the first 9 found from the left results in the maximum number.

Solution

To solve this problem, the approach revolves around identifying the most significant digit that can be increased by a swap. We traverse the number from right to left, identifying the largest digit seen so far and its index. This is because a larger digit appearing later in the number, when swapped with a smaller digit to its left, will yield a greater value. The key is to find the leftmost digit for which a larger digit exists anywhere to its right. Swapping these two digits will result in the maximum possible number. This approach is effective as it minimizes the swaps and ensures the largest digit possible in the highest place value.

Step-by-Step Algorithm

  1. Convert the given number into an array of its digits for easier manipulation.

  2. Prepare the maxIndexAfter Array:

    • Initialize an array maxIndexAfter to record the index of the maximum digit found to the right of each digit (including itself).
    • Traverse the digit array from right to left.
    • Update maxIndexAfter for each position with the index of the largest digit seen so far.
  3. Perform the Swap:

    • Traverse the digits array from left to right.
    • If digits[i] and digits[maxIndexAfter[i]] are not same, swap both elements.
    • After the first swap, break the loop.
  4. Reconstruct the Number: Convert the digit array back into a single integer.

  5. Return the Result: Provide the modified number as the output.

Algorithm Walkthrough

Consider the Input 7281912.

  1. Initialization:

    • Convert to digit array: [7, 2, 8, 1, 9, 1, 2].
    • Initialize maxIndexAfter array with the same length as the digit array.
  2. Preparing the maxIndexAfter Array:

    • Start from the rightmost digit.
    • Iteration 1 (Index 6): Digit 2, maxIndexAfter[6] = 6.
    • Iteration 2 (Index 5): Digit 1, maxIndexAfter[5] = 6 (as 2 is the maximum seen so far).
    • Iteration 3 (Index 4): Digit 9, maxIndexAfter[4] = 4.
    • Continue updating maxIndexAfter for each digit.
    • Final maxIndexAfter array: [4, 4, 4, 4, 4, 6, 6].
  3. Performing the Swap:

    • Traverse from left to right.
    • Iteration 1 (Index 0): Digit 7, compare with maxIndexAfter[0] (digit at index 4 which is 9), so swap them.
    • As soon as the first swap opportunity is found, break the loop.
    • Array after swap: [9, 2, 8, 1, 7, 1, 2].
  4. Reconstructing the Number:

    • Convert array back to number: 9281712.
  5. Returning the Result:

    • Return 9281712.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity: O(n)

The process of converting the number to a digit array and traversing it (both for preparing maxIndexAfter and finding the swap position) each take O(n) time, linearly dependent on the number of digits (n).

Space Complexity: O(n)

The algorithm requires space proportional to the number of digits (n) for storing the digit array and the maxIndexAfter array, leading to O(n) space complexity.

Maximum Swap (medium)
Custom Sort String (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)